package Review.Linklist;
//双链表
public class MyLinkedList {

//相关的节点结构
    class ListNode {
        int val;
        ListNode next, prev;

        ListNode(int val) {
            this.val = val;
        }
    }
    private int size;
    private ListNode head,tail;
    //初始化
    public MyLinkedList() {

        this.size = 0;
        this.head=new ListNode(0);
        this.tail=new ListNode(0);
        this.head.next=tail;
        this.tail.prev=head;
    }
    public int get(int index){
        if(index<0 || index>=size){
            return -1;
        }
        ListNode cur=head;
        //判断那边循环最快
        if(index>=size/2){
            cur=tail;
            for(int i=0;i<size-index;i++){
                cur=cur.prev;
            }
        }
        else{
            for(int i=0;i<index;i++){
                cur=cur.next;
            }
        }
        return cur.val;
    }
    public void addAtHead(int val) {
        addAtIndex(0,val);
    }
    public void addAtTail(int val) {
        addAtIndex(size,val);
    }
    //根据索引添加值
    public void addAtIndex(int index, int val) {
        if(index<0 || index>=size){
            return;
        }
        ListNode newNode=new ListNode(val);
        //找到前驱
        ListNode pre=head;
        for(int i=0;i<index;i++){
            pre=pre.next;
        }
        newNode.next=pre.next;
        pre.next=newNode;
        newNode.prev=pre;
        pre.next=newNode;
        size++;
    }
    public void deleteAtIndex(int index) {
        if(index<0 || index>=size){
            return;
        }
        ListNode pre=head;
        for(int i=0;i<index;i++){
            pre=pre.next;
        }
        pre.next.next.prev=pre.prev;
        pre.next=pre.next.next;
        size--;

    }


}

